package problem494;//dfs版

//494.目标和
//https://leetcode.cn/problems/target-sum/

class Solution1 {
    int n = 0, sum = 0, count = 0, aim = 0;
    public int findTargetSumWays(int[] nums, int target) {
        n = nums.length;
        aim = target;
        dfs(0, nums);
        return count;
    }
    public void dfs(int u, int[] nums) {
        if(u == n) {
            if(sum == aim) count++;
            return;
        }
        //添加+
        sum += nums[u];
        dfs(u+1, nums);
        //回溯
        sum -= nums[u];

        //添加-
        sum -= nums[u];
        dfs(u+1, nums);
        //回溯
        sum += nums[u];
    }
}
